#include <iostream>
#include <vector>

using namespace std;
class Solution
{
public:
    /**
     * @brief heap buffer overflow
     *  递归多次调用不行
     * @param grid
     * @param k
     * @return vector<vector<int>>
     */
    vector<vector<int>> shiftGrid_0(vector<vector<int>> &grid, int k)
    {
        if (!k)
        {
            return grid;
        }

        auto shiftK = [](vector<vector<int>> &grid) -> vector<vector<int>>
        {
            int m = grid.size(), n = grid[0].size();
            vector<vector<int>> ans(m, vector<int>(n, 0));
            for (int i = 0; i < m; i++)
            {
                for (size_t j = 0; j < n; j++)
                {
                    ans[i][j + 1] = grid[i][j];
                }
                if (i + 1 < m)
                {
                    ans[i + 1][0] = grid[i][n - 1];
                }
            }
            ans[0][0] = grid[m - 1][n - 1];
            return ans;
        };
        vector<vector<int>> res = shiftK(grid);
        while (k - 1)
        {
            res = shiftK(res);
            k--;
        }

        return res;
    }
    /**
     * @brief 一维展开
     * 
     * @param grid 
     * @param k 
     * @return vector<vector<int>> 
     */
    vector<vector<int>> shiftGrid(vector<vector<int>> &grid, int k)
    {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> ret(m, vector<int>(n));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int index = (i * n + j + k) % (m * n);
                ret[index / n][index % n] = grid[i][j];
            }
        }
        return ret;
    }
};
int main()
{
    Solution s;
    vector<vector<int>> grid = {{3, 8, 1, 9}, {19, 7, 2, 5}, {4, 6, 11, 10}, {12, 0, 21, 13}};
    int k = 4;
    vector<vector<int>> ans = s.shiftGrid(grid, k);
    for (vector<int> row : ans)
    {
        for (int e : row)
        {
            cout << e << " ";
        }
        cout << endl;
    }
    return 0;
}